#include <stdio.h>
#include <malloc.h>
#include <windows.h>

#define MAXSIZE 100
#define OK 1
typedef int Status;
typedef int KeyType; //整型关键字类型
typedef struct BNode {
    KeyType key; //存储块中记录的关键字值
    struct BNode *next; //指向块链中下一记录结点的指针
} BNode; //块链中的结点类型
typedef struct SNode {
    KeyType Maxkey; //存储各块记录中的最大关键字值
    BNode *head; //块链的头指针
} SNode; //索引表中元素的类型
typedef struct {
    SNode r[MAXSIZE]; //用于存放索引表中块元素的数组
    int length; //用于存放索引表中块的个数
} STable; //索引查找表的结构类型

void setup() {
    // 设置控制台代码页为UTF-8
    SetConsoleOutputCP(CP_UTF8);
    // 设置控制台输入代码页为UTF-8
    SetConsoleCP(CP_UTF8);
    setvbuf(stdout, NULL, _IONBF, 0); // 设置为无缓冲模式
}

Status Init_STable(STable &ST) //构造一个空的索引表
{
    for (int i = 1; i <= MAXSIZE; i++)
        ST.r[i].head = NULL;
    ST.length = 0;
    return OK;
} //Creat_SSTable

Status Creat_STable(STable &ST) {
    BNode *p, *q;
    KeyType max, node;
    int i;
    printf("请输入索引表块数:");
    scanf("%d", &ST.length);
    for (i = 1; i <= ST.length; i++) {
        if (i == 1) {
            scanf("%d", &node);
            p = (BNode *) malloc(sizeof(BNode));
            p->key = node;
            p->next = NULL;
            ST.r[i].head = p;
            max = p->key;
            q = p;
            scanf("%d", &node);
            while (node != 0) {
                p = (BNode *) malloc(sizeof(BNode));
                p->key = node;
                q->next = p;
                q = p;
                if (max < p->key) max = p->key;
                scanf("%d", &node);
            }
            q->next = NULL;
            ST.r[i].Maxkey = max;
        } else {
            scanf("%d", &node);
            while (node < ST.r[i - 1].Maxkey) {
                printf("小于前一块的最大关键字，请重新输入\n");
                scanf("%d", &node);
            }
            p = (BNode *) malloc(sizeof(BNode));
            p->key = node;
            p->next = NULL;
            ST.r[i].head = p;
            max = p->key;
            q = p;
            scanf("%d", &node);
            while (node != 0) {
                p = (BNode *) malloc(sizeof(BNode));
                while (node < ST.r[i - 1].Maxkey) {
                    printf("小于前一块的最大关键字，请重新输入\n");
                    scanf("%d", &node);
                }
                p->key = node;
                q->next = p;
                q = p;
                if (max < p->key) max = p->key;
                scanf("%d", &node);
            }
            q->next = NULL;
            ST.r[i].Maxkey = max;
        }
    }
    return OK;
}

Status Display(STable ST) {
    int i;
    BNode *p;
    for (i = 1; i <= ST.length; i++) {
        printf("第%d块,最大关键字为%d:", i, ST.r[i].Maxkey);
        printf("分别为:");
        p = ST.r[i].head;
        while (p) {
            printf("%d  ", p->key);
            p = p->next;
        }
        printf("\n");
    }
    return OK;
}

int FindBlock(STable ST, KeyType key)
//用二分查找法在索引查找表ST的索引表中确定关键字值为key的待查找记录所在的块号,
//函数并返回值其块号值
{
    int low, high, mid;
    low = 1;
    high = ST.length;
    while (low <= high) {
        mid = (low + high) / 2;
        if (key == ST.r[mid].Maxkey)
            return mid;
        else if (key < ST.r[mid].Maxkey)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return high + 1;
} // FindBlock

Status FindRec(STable ST, KeyType key, int &Bno, int &pos)
//用顺序查找法在索引查找表的块链中确定关键字值为key的待查找记录的存储位置
//如果查找成功，记录所在的快号和在快中的位序号分别为Bno和pos，否则都为0
{
    BNode *p;
    int i = 1;
    Bno = FindBlock(ST, key); //调用函数，确定待查记录所在块号
    p = ST.r[Bno].head; //取到待查记录所在块链的头指针
    while (p && p->key != key) //顺着链指针依次查找
    {
        p = p->next;
        i++;
    }
    if (p)
        pos = i; //查找成功，在快中的位置为i
    else
        pos = 0; //查找不成功，在快中的位置为0
    return OK;
} //FindRec

int main() {
    setup();
    STable ST;
    KeyType key;
    int Bno, pos, e;
    Init_STable(ST);
    Creat_STable(ST);
    Display(ST);
    do {
        printf("请输入要查找的关键值:");
        scanf("%d", &key);
        FindRec(ST, key, Bno, pos);
        if (pos == 0)
            printf("%d查找未成功\n", key);
        else
            printf("%d在第%d块的第%d个位置\n", key, Bno, pos);
        printf("还要继续查找吗？是的话，输入1，不是的话输入0\n");
        scanf("%d", &e);
        if (e == 0)
            break;
    } while (e == 1);

    return 0;
}
